Search Results

Documents authored by Kobayashi, Yusuke

Document
DOI: 10.4230/LIPIcs.ISAAC.2023.48
Reconfiguration of the Union of Arborescences

Authors: Yusuke Kobayashi, Ryoga Mahara, and Tamás Schwarcz

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
An arborescence in a digraph is an acyclic arc subset in which every vertex except a root has exactly one incoming arc. In this paper, we show the reconfigurability of the union of k arborescences for fixed k in the following sense: for any pair of arc subsets that can be partitioned into k arborescences, one can be transformed into the other by exchanging arcs one by one so that every intermediate arc subset can also be partitioned into k arborescences. This generalizes the result by Ito et al. (2023), who showed the case with k = 1. Since the union of k arborescences can be represented as a common matroid basis of two matroids, our result gives a new non-trivial example of matroid pairs for which two common bases are always reconfigurable to each other.
Cite as

Yusuke Kobayashi, Ryoga Mahara, and Tamás Schwarcz. Reconfiguration of the Union of Arborescences. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 48:1-48:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kobayashi_et_al:LIPIcs.ISAAC.2023.48,
  author =	{Kobayashi, Yusuke and Mahara, Ryoga and Schwarcz, Tam\'{a}s},
  title =	{{Reconfiguration of the Union of Arborescences}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{48:1--48:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.48},
  URN =		{urn:nbn:de:0030-drops-193502},
  doi =		{10.4230/LIPIcs.ISAAC.2023.48},
  annote =	{Keywords: Arborescence packing, common matroid basis, combinatorial reconfiguration}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2023.49
An Approximation Algorithm for Two-Edge-Connected Subgraph Problem via Triangle-Free Two-Edge-Cover

Authors: Yusuke Kobayashi and Takashi Noguchi

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
The 2-Edge-Connected Spanning Subgraph problem (2-ECSS) is one of the most fundamental and well-studied problems in the context of network design. We are given an undirected graph G, and the objective is to find a 2-edge-connected spanning subgraph H of G with the minimum number of edges. For this problem, a lot of approximation algorithms have been proposed in the literature. In particular, very recently, Garg, Grandoni, and Ameli gave an approximation algorithm for 2-ECSS with a factor of 1.326, which is the best approximation ratio. In this paper, under the assumption that a maximum triangle-free 2-matching can be found in polynomial time in a graph, we give a (1.3+ε)-approximation algorithm for 2-ECSS, where ε is an arbitrarily small positive fixed constant. Note that a complicated polynomial-time algorithm for finding a maximum triangle-free 2-matching is announced by Hartvigsen in his PhD thesis, but it has not been peer-reviewed or checked in any other way. In our algorithm, we compute a minimum triangle-free 2-edge-cover in G with the aid of the algorithm for finding a maximum triangle-free 2-matching. Then, with the obtained triangle-free 2-edge-cover, we apply the arguments by Garg, Grandoni, and Ameli.
Cite as

Yusuke Kobayashi and Takashi Noguchi. An Approximation Algorithm for Two-Edge-Connected Subgraph Problem via Triangle-Free Two-Edge-Cover. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 49:1-49:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kobayashi_et_al:LIPIcs.ISAAC.2023.49,
  author =	{Kobayashi, Yusuke and Noguchi, Takashi},
  title =	{{An Approximation Algorithm for Two-Edge-Connected Subgraph Problem via Triangle-Free Two-Edge-Cover}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{49:1--49:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.49},
  URN =		{urn:nbn:de:0030-drops-193514},
  doi =		{10.4230/LIPIcs.ISAAC.2023.49},
  annote =	{Keywords: approximation algorithm, survivable network design, minimum 2-edge-connected spanning subgraph, triangle-free 2-matching}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.81
Rerouting Planar Curves and Disjoint Paths

Authors: Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
In this paper, we consider a transformation of k disjoint paths in a graph. For a graph and a pair of k disjoint paths 𝒫 and 𝒬 connecting the same set of terminal pairs, we aim to determine whether 𝒫 can be transformed to 𝒬 by repeatedly replacing one path with another path so that the intermediates are also k disjoint paths. The problem is called Disjoint Paths Reconfiguration. We first show that Disjoint Paths Reconfiguration is PSPACE-complete even when k = 2. On the other hand, we prove that, when the graph is embedded on a plane and all paths in 𝒫 and 𝒬 connect the boundaries of two faces, Disjoint Paths Reconfiguration can be solved in polynomial time. The algorithm is based on a topological characterization for rerouting curves on a plane using the algebraic intersection number. We also consider a transformation of disjoint s-t paths as a variant. We show that the disjoint s-t paths reconfiguration problem in planar graphs can be determined in polynomial time, while the problem is PSPACE-complete in general.
Cite as

Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki. Rerouting Planar Curves and Disjoint Paths. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 81:1-81:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{ito_et_al:LIPIcs.ICALP.2023.81,
  author =	{Ito, Takehiro and Iwamasa, Yuni and Kakimura, Naonori and Kobayashi, Yusuke and Maezawa, Shun-ichi and Nozaki, Yuta and Okamoto, Yoshio and Ozeki, Kenta},
  title =	{{Rerouting Planar Curves and Disjoint Paths}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{81:1--81:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.81},
  URN =		{urn:nbn:de:0030-drops-181339},
  doi =		{10.4230/LIPIcs.ICALP.2023.81},
  annote =	{Keywords: Disjoint paths, combinatorial reconfiguration, planar graphs}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.82
Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra

Authors: Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, and Yoshio Okamoto

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
We prove that the computation of a combinatorial shortest path between two vertices of a graph associahedron, introduced by Carr and Devadoss, is NP-hard. This resolves an open problem raised by Cardinal. A graph associahedron is a generalization of the well-known associahedron. The associahedron is obtained as the graph associahedron of a path. It is a tantalizing and important open problem in theoretical computer science whether the computation of a combinatorial shortest path between two vertices of the associahedron can be done in polynomial time, which is identical to the computation of the flip distance between two triangulations of a convex polygon, and the rotation distance between two rooted binary trees. Our result shows that a certain generalized approach to tackling this open problem is not promising. As a corollary of our theorem, we prove that the computation of a combinatorial shortest path between two vertices of a polymatroid base polytope cannot be done in polynomial time unless P = NP. Since a combinatorial shortest path on the matroid base polytope can be computed in polynomial time, our result reveals an unexpected contrast between matroids and polymatroids.
Cite as

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, and Yoshio Okamoto. Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 82:1-82:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{ito_et_al:LIPIcs.ICALP.2023.82,
  author =	{Ito, Takehiro and Kakimura, Naonori and Kamiyama, Naoyuki and Kobayashi, Yusuke and Maezawa, Shun-ichi and Nozaki, Yuta and Okamoto, Yoshio},
  title =	{{Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{82:1--82:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.82},
  URN =		{urn:nbn:de:0030-drops-181344},
  doi =		{10.4230/LIPIcs.ICALP.2023.82},
  annote =	{Keywords: Graph associahedra, combinatorial shortest path, NP-hardness, polymatroids}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.43
Reconfiguration of Colorings in Triangulations of the Sphere

Authors: Takehiro Ito, Yuni Iwamasa, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
In 1973, Fisk proved that any 4-coloring of a 3-colorable triangulation of the 2-sphere can be obtained from any 3-coloring by a sequence of Kempe-changes. On the other hand, in the case where we are only allowed to recolor a single vertex in each step, which is a special case of a Kempe-change, there exists a 4-coloring that cannot be obtained from any 3-coloring. In this paper, we present a linear-time checkable characterization of a 4-coloring of a 3-colorable triangulation of the 2-sphere that can be obtained from a 3-coloring by a sequence of recoloring operations at single vertices. In addition, we develop a quadratic-time algorithm to find such a recoloring sequence if it exists; our proof implies that we can always obtain a quadratic length recoloring sequence. We also present a linear-time checkable criterion for a 3-colorable triangulation of the 2-sphere that all 4-colorings can be obtained from a 3-coloring by such a sequence. Moreover, we consider a high-dimensional setting. As a natural generalization of our first result, we obtain a polynomial-time checkable characterization of a k-coloring of a (k-1)-colorable triangulation of the (k-2)-sphere that can be obtained from a (k-1)-coloring by a sequence of recoloring operations at single vertices and the corresponding algorithmic result. Furthermore, we show that the problem of deciding whether, for given two (k+1)-colorings of a (k-1)-colorable triangulation of the (k-2)-sphere, one can be obtained from the other by such a sequence is PSPACE-complete for any fixed k ≥ 4. Our results above can be rephrased as new results on the computational problems named k-Recoloring and Connectedness of k-Coloring Reconfiguration Graph, which are fundamental problems in the field of combinatorial reconfiguration.
Cite as

Takehiro Ito, Yuni Iwamasa, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki. Reconfiguration of Colorings in Triangulations of the Sphere. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 43:1-43:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{ito_et_al:LIPIcs.SoCG.2023.43,
  author =	{Ito, Takehiro and Iwamasa, Yuni and Kobayashi, Yusuke and Maezawa, Shun-ichi and Nozaki, Yuta and Okamoto, Yoshio and Ozeki, Kenta},
  title =	{{Reconfiguration of Colorings in Triangulations of the Sphere}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{43:1--43:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.43},
  URN =		{urn:nbn:de:0030-drops-178936},
  doi =		{10.4230/LIPIcs.SoCG.2023.43},
  annote =	{Keywords: Graph coloring, Triangulation of the sphere, Combinatorial reconfiguration}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.47
One-Face Shortest Disjoint Paths with a Deviation Terminal

Authors: Yusuke Kobayashi and Tatsuya Terao

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
For an undirected graph G and distinct vertices s₁, t₁, … , s_k, t_k called terminals, the shortest k-disjoint paths problem asks for k pairwise vertex-disjoint paths P₁, … , P_k such that P_i connects s_i and t_i for i = 1, … , k and the sum of their lengths is minimized. This problem is a natural optimization version of the well-known k-disjoint paths problem, and its polynomial solvability is widely open. One of the best results on the shortest k-disjoint paths problem is due to Datta et al. [Datta et al., 2018], who present a polynomial-time algorithm for the case when G is planar and all the terminals are on one face. In this paper, we extend this result by giving a polynomial-time randomized algorithm for the case when all the terminals except one are on some face of G. In our algorithm, we combine the arguments of Datta et al. with some results on the shortest disjoint (A + B)-paths problem shown by Hirai and Namba [Hirai and Namba, 2018]. To this end, we present a non-trivial bijection between k disjoint paths and disjoint (A + B)-paths, which is a key technical contribution of this paper.
Cite as

Yusuke Kobayashi and Tatsuya Terao. One-Face Shortest Disjoint Paths with a Deviation Terminal. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 47:1-47:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kobayashi_et_al:LIPIcs.ISAAC.2022.47,
  author =	{Kobayashi, Yusuke and Terao, Tatsuya},
  title =	{{One-Face Shortest Disjoint Paths with a Deviation Terminal}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{47:1--47:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.47},
  URN =		{urn:nbn:de:0030-drops-173322},
  doi =		{10.4230/LIPIcs.ISAAC.2022.47},
  annote =	{Keywords: shortest disjoint paths, polynomial time algorithm, planar graph}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.55
Proportional Allocation of Indivisible Goods up to the Least Valued Good on Average

Authors: Yusuke Kobayashi and Ryoga Mahara

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
We study the problem of fairly allocating a set of indivisible goods to multiple agents and focus on the proportionality, which is one of the classical fairness notions. Since proportional allocations do not always exist when goods are indivisible, approximate notions of proportionality have been considered in the previous work. Among them, proportionality up to the maximin good (PROPm) has been the best approximate notion of proportionality that can be achieved for all instances. In this paper, we introduce the notion of proportionality up to the least valued good on average (PROPavg), which is a stronger notion than PROPm, and show that a PROPavg allocation always exists. Our results establish PROPavg as a notable non-trivial fairness notion that can be achieved for all instances. Our proof is constructive, and based on a new technique that generalizes the cut-and-choose protocol.
Cite as

Yusuke Kobayashi and Ryoga Mahara. Proportional Allocation of Indivisible Goods up to the Least Valued Good on Average. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 55:1-55:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kobayashi_et_al:LIPIcs.ISAAC.2022.55,
  author =	{Kobayashi, Yusuke and Mahara, Ryoga},
  title =	{{Proportional Allocation of Indivisible Goods up to the Least Valued Good on Average}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{55:1--55:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.55},
  URN =		{urn:nbn:de:0030-drops-173402},
  doi =		{10.4230/LIPIcs.ISAAC.2022.55},
  annote =	{Keywords: Discrete Fair Division, Indivisible Goods, Proportionality}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.15
Reconfiguration of Spanning Trees with Degree Constraint or Diameter Constraint

Authors: Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki, and Kunihiro Wasa

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
We investigate the complexity of finding a transformation from a given spanning tree in a graph to another given spanning tree in the same graph via a sequence of edge flips. The exchange property of the matroid bases immediately yields that such a transformation always exists if we have no constraints on spanning trees. In this paper, we wish to find a transformation which passes through only spanning trees satisfying some constraint. Our focus is bounding either the maximum degree or the diameter of spanning trees, and we give the following results. The problem with a lower bound on maximum degree is solvable in polynomial time, while the problem with an upper bound on maximum degree is PSPACE-complete. The problem with a lower bound on diameter is NP-hard, while the problem with an upper bound on diameter is solvable in polynomial time.
Cite as

Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki, and Kunihiro Wasa. Reconfiguration of Spanning Trees with Degree Constraint or Diameter Constraint. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 15:1-15:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.STACS.2022.15,
  author =	{Bousquet, Nicolas and Ito, Takehiro and Kobayashi, Yusuke and Mizuta, Haruka and Ouvrard, Paul and Suzuki, Akira and Wasa, Kunihiro},
  title =	{{Reconfiguration of Spanning Trees with Degree Constraint or Diameter Constraint}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{15:1--15:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.15},
  URN =		{urn:nbn:de:0030-drops-158253},
  doi =		{10.4230/LIPIcs.STACS.2022.15},
  annote =	{Keywords: combinatorial reconfiguration, spanning trees, PSPACE, polynomial-time algorithms}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2020.15
Fixed-Parameter Algorithms for Graph Constraint Logic

Authors: Tatsuhiko Hatanaka, Felix Hommelsheim, Takehiro Ito, Yusuke Kobayashi, Moritz Mühlenthaler, and Akira Suzuki

Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)

Abstract
Non-deterministic constraint logic (NCL) is a simple model of computation based on orientations of a constraint graph with edge weights and vertex demands. NCL captures PSPACE and has been a useful tool for proving algorithmic hardness of many puzzles, games, and reconfiguration problems. In particular, its usefulness stems from the fact that it remains PSPACE-complete even under severe restrictions of the weights (e.g., only edge-weights one and two are needed) and the structure of the constraint graph (e.g., planar AND/OR graphs of bounded bandwidth). While such restrictions on the structure of constraint graphs do not seem to limit the expressiveness of NCL, the building blocks of the constraint graphs cannot be limited without losing expressiveness: We consider as parameters the number of weight-one edges and the number of weight-two edges of a constraint graph, as well as the number of AND or OR vertices of an AND/OR constraint graph. We show that NCL is fixed-parameter tractable (FPT) for any of these parameters. In particular, for NCL parameterized by the number of weight-one edges or the number of AND vertices, we obtain a linear kernel. It follows that, in a sense, NCL as introduced by Hearn and Demaine is defined in the most economical way for the purpose of capturing PSPACE.
Cite as

Tatsuhiko Hatanaka, Felix Hommelsheim, Takehiro Ito, Yusuke Kobayashi, Moritz Mühlenthaler, and Akira Suzuki. Fixed-Parameter Algorithms for Graph Constraint Logic. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{hatanaka_et_al:LIPIcs.IPEC.2020.15,
  author =	{Hatanaka, Tatsuhiko and Hommelsheim, Felix and Ito, Takehiro and Kobayashi, Yusuke and M\"{u}hlenthaler, Moritz and Suzuki, Akira},
  title =	{{Fixed-Parameter Algorithms for Graph Constraint Logic}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{15:1--15:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Cao, Yixin and Pilipczuk, Marcin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.15},
  URN =		{urn:nbn:de:0030-drops-133182},
  doi =		{10.4230/LIPIcs.IPEC.2020.15},
  annote =	{Keywords: Combinatorial Reconfiguration, Nondeterministic Constraint Logic, Fixed Parameter Tractability}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.39
Market Pricing for Matroid Rank Valuations

Authors: Kristóf Bérczi, Naonori Kakimura, and Yusuke Kobayashi

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
In this paper, we study the problem of maximizing social welfare in combinatorial markets through pricing schemes. We consider the existence of prices that are capable to achieve optimal social welfare without a central tie-breaking coordinator. In the case of two buyers with matroid rank valuations, we give polynomial-time algorithms that always find such prices when one of the matroids is a simple partition matroid or both matroids are strongly base orderable. This result partially answers a question raised by Düetting and Végh in 2017. We further formalize a weighted variant of the conjecture of Düetting and Végh, and show that the weighted variant can be reduced to the unweighted one based on the weight-splitting theorem for weighted matroid intersection by Frank. We also show that a similar reduction technique works for M^♮-concave functions, or equivalently, for gross substitutes functions.
Cite as

Kristóf Bérczi, Naonori Kakimura, and Yusuke Kobayashi. Market Pricing for Matroid Rank Valuations. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{berczi_et_al:LIPIcs.ISAAC.2020.39,
  author =	{B\'{e}rczi, Krist\'{o}f and Kakimura, Naonori and Kobayashi, Yusuke},
  title =	{{Market Pricing for Matroid Rank Valuations}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{39:1--39:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.39},
  URN =		{urn:nbn:de:0030-drops-133833},
  doi =		{10.4230/LIPIcs.ISAAC.2020.39},
  annote =	{Keywords: Pricing schemes, Walrasian equilibrium, gross substitutes valuations, matroid rank functions}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.24
Reconfiguration of Spanning Trees with Many or Few Leaves

Authors: Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki, and Kunihiro Wasa

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
Let G be a graph and T₁,T₂ be two spanning trees of G. We say that T₁ can be transformed into T₂ via an edge flip if there exist two edges e ∈ T₁ and f in T₂ such that T₂ = (T₁⧵e) ∪ f. Since spanning trees form a matroid, one can indeed transform a spanning tree into any other via a sequence of edge flips, as observed in [Takehiro Ito et al., 2011]. We investigate the problem of determining, given two spanning trees T₁,T₂ with an additional property Π, if there exists an edge flip transformation from T₁ to T₂ keeping property Π all along. First we show that determining if there exists a transformation from T₁ to T₂ such that all the trees of the sequence have at most k (for any fixed k ≥ 3) leaves is PSPACE-complete. We then prove that determining if there exists a transformation from T₁ to T₂ such that all the trees of the sequence have at least k leaves (where k is part of the input) is PSPACE-complete even restricted to split, bipartite or planar graphs. We complete this result by showing that the problem becomes polynomial for cographs, interval graphs and when k = n-2.
Cite as

Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki, and Kunihiro Wasa. Reconfiguration of Spanning Trees with Many or Few Leaves. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bousquet_et_al:LIPIcs.ESA.2020.24,
  author =	{Bousquet, Nicolas and Ito, Takehiro and Kobayashi, Yusuke and Mizuta, Haruka and Ouvrard, Paul and Suzuki, Akira and Wasa, Kunihiro},
  title =	{{Reconfiguration of Spanning Trees with Many or Few Leaves}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{24:1--24:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.24},
  URN =		{urn:nbn:de:0030-drops-128909},
  doi =		{10.4230/LIPIcs.ESA.2020.24},
  annote =	{Keywords: combinatorial reconfiguration, spanning trees, PSPACE, polynomial-time algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.11
An FPT Algorithm for Minimum Additive Spanner Problem

Authors: Yusuke Kobayashi

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
For a positive integer t and a graph G, an additive t-spanner of G is a spanning subgraph in which the distance between every pair of vertices is at most the original distance plus t. The Minimum Additive t-Spanner Problem is to find an additive t-spanner with the minimum number of edges in a given graph, which is known to be NP-hard. Since we need to care about global properties of graphs when we deal with additive t-spanners, the Minimum Additive t-Spanner Problem is hard to handle and hence only few results are known for it. In this paper, we study the Minimum Additive t-Spanner Problem from the viewpoint of parameterized complexity. We formulate a parameterized version of the problem in which the number of removed edges is regarded as a parameter, and give a fixed-parameter algorithm for it. We also extend our result to the case with both a multiplicative approximation factor α and an additive approximation parameter β, which we call (α, β)-spanners.
Cite as

Yusuke Kobayashi. An FPT Algorithm for Minimum Additive Spanner Problem. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kobayashi:LIPIcs.STACS.2020.11,
  author =	{Kobayashi, Yusuke},
  title =	{{An FPT Algorithm for Minimum Additive Spanner Problem}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{11:1--11:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.11},
  URN =		{urn:nbn:de:0030-drops-118729},
  doi =		{10.4230/LIPIcs.STACS.2020.11},
  annote =	{Keywords: Graph algorithms, Fixed-parameter tractability, Graph spanner}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.35
Shortest Reconfiguration of Colorings Under Kempe Changes

Authors: Marthe Bonamy, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Moritz Mühlenthaler, Akira Suzuki, and Kunihiro Wasa

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
A k-coloring of a graph maps each vertex of the graph to a color in {1, 2, …, k}, such that no two adjacent vertices receive the same color. Given a k-coloring of a graph, a Kempe change produces a new k-coloring by swapping the colors in a bicolored connected component. We investigate the complexity of finding the smallest number of Kempe changes needed to transform a given k-coloring into another given k-coloring. We show that this problem admits a polynomial-time dynamic programming algorithm on path graphs, which turns out to be highly non-trivial. Furthermore, the problem is NP-hard even on star graphs and we show that on such graphs it admits a constant-factor approximation algorithm and is fixed-parameter tractable when parameterized by the number k of colors. The hardness result as well as the algorithmic results are based on the notion of a canonical transformation.
Cite as

Marthe Bonamy, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Moritz Mühlenthaler, Akira Suzuki, and Kunihiro Wasa. Shortest Reconfiguration of Colorings Under Kempe Changes. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 35:1-35:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bonamy_et_al:LIPIcs.STACS.2020.35,
  author =	{Bonamy, Marthe and Heinrich, Marc and Ito, Takehiro and Kobayashi, Yusuke and Mizuta, Haruka and M\"{u}hlenthaler, Moritz and Suzuki, Akira and Wasa, Kunihiro},
  title =	{{Shortest Reconfiguration of Colorings Under Kempe Changes}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{35:1--35:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.35},
  URN =		{urn:nbn:de:0030-drops-118961},
  doi =		{10.4230/LIPIcs.STACS.2020.35},
  annote =	{Keywords: Combinatorial Reconfiguration, Graph Algorithms, Graph Coloring, Kempe Equivalence}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2019.13
Parameterized Algorithms for Maximum Cut with Connectivity Constraints

Authors: Hiroshi Eto, Tesshu Hanaka, Yasuaki Kobayashi, and Yusuke Kobayashi

Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

Abstract
We study two variants of Maximum Cut, which we call Connected Maximum Cut and Maximum Minimal Cut, in this paper. In these problems, given an unweighted graph, the goal is to compute a maximum cut satisfying some connectivity requirements. Both problems are known to be NP-complete even on planar graphs whereas Maximum Cut on planar graphs is solvable in polynomial time. We first show that these problems are NP-complete even on planar bipartite graphs and split graphs. Then we give parameterized algorithms using graph parameters such as clique-width, tree-width, and twin-cover number. Finally, we obtain FPT algorithms with respect to the solution size.
Cite as

Hiroshi Eto, Tesshu Hanaka, Yasuaki Kobayashi, and Yusuke Kobayashi. Parameterized Algorithms for Maximum Cut with Connectivity Constraints. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 13:1-13:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{eto_et_al:LIPIcs.IPEC.2019.13,
  author =	{Eto, Hiroshi and Hanaka, Tesshu and Kobayashi, Yasuaki and Kobayashi, Yusuke},
  title =	{{Parameterized Algorithms for Maximum Cut with Connectivity Constraints}},
  booktitle =	{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
  pages =	{13:1--13:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-129-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{148},
  editor =	{Jansen, Bart M. P. and Telle, Jan Arne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.13},
  URN =		{urn:nbn:de:0030-drops-114747},
  doi =		{10.4230/LIPIcs.IPEC.2019.13},
  annote =	{Keywords: Maximum cut, Parameterized algorithm, NP-hardness, Graph parameter}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2019.22
Improved Analysis of Highest-Degree Branching for Feedback Vertex Set

Authors: Yoichi Iwata and Yusuke Kobayashi

Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)

Abstract
Recent empirical evaluations of exact algorithms for Feedback Vertex Set have demonstrated the efficiency of a highest-degree branching algorithm with a degree-based pruning heuristic. In this paper, we prove that this empirically fast algorithm runs in O(3.460^k n) time, where k is the solution size. This improves the previous best O(3.619^k n)-time deterministic algorithm obtained by Kociumaka and Pilipczuk (Inf. Process. Lett., 2014).
Cite as

Yoichi Iwata and Yusuke Kobayashi. Improved Analysis of Highest-Degree Branching for Feedback Vertex Set. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 22:1-22:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{iwata_et_al:LIPIcs.IPEC.2019.22,
  author =	{Iwata, Yoichi and Kobayashi, Yusuke},
  title =	{{Improved Analysis of Highest-Degree Branching for Feedback Vertex Set}},
  booktitle =	{14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
  pages =	{22:1--22:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-129-0},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{148},
  editor =	{Jansen, Bart M. P. and Telle, Jan Arne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.22},
  URN =		{urn:nbn:de:0030-drops-114833},
  doi =		{10.4230/LIPIcs.IPEC.2019.22},
  annote =	{Keywords: Feedback Vertex Set, Branch and bound, Measure and conquer}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.61
Shortest Reconfiguration of Perfect Matchings via Alternating Cycles

Authors: Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
Motivated by adjacency in perfect matching polytopes, we study the shortest reconfiguration problem of perfect matchings via alternating cycles. Namely, we want to find a shortest sequence of perfect matchings which transforms one given perfect matching to another given perfect matching such that the symmetric difference of each pair of consecutive perfect matchings is a single cycle. The problem is equivalent to the combinatorial shortest path problem in perfect matching polytopes. We prove that the problem is NP-hard even when a given graph is planar or bipartite, but it can be solved in polynomial time when the graph is outerplanar.
Cite as

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto. Shortest Reconfiguration of Perfect Matchings via Alternating Cycles. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 61:1-61:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{ito_et_al:LIPIcs.ESA.2019.61,
  author =	{Ito, Takehiro and Kakimura, Naonori and Kamiyama, Naoyuki and Kobayashi, Yusuke and Okamoto, Yoshio},
  title =	{{Shortest Reconfiguration of Perfect Matchings via Alternating Cycles}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{61:1--61:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.61},
  URN =		{urn:nbn:de:0030-drops-111823},
  doi =		{10.4230/LIPIcs.ESA.2019.61},
  annote =	{Keywords: Matching, Combinatorial reconfiguration, Alternating cycles, Combinatorial shortest paths}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2019.80
The Perfect Matching Reconfiguration Problem

Authors: Marthe Bonamy, Nicolas Bousquet, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Arnaud Mary, Moritz Mühlenthaler, and Kunihiro Wasa

Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Abstract
We study the perfect matching reconfiguration problem: Given two perfect matchings of a graph, is there a sequence of flip operations that transforms one into the other? Here, a flip operation exchanges the edges in an alternating cycle of length four. We are interested in the complexity of this decision problem from the viewpoint of graph classes. We first prove that the problem is PSPACE-complete even for split graphs and for bipartite graphs of bounded bandwidth with maximum degree five. We then investigate polynomial-time solvable cases. Specifically, we prove that the problem is solvable in polynomial time for strongly orderable graphs (that include interval graphs and strongly chordal graphs), for outerplanar graphs, and for cographs (also known as P_4-free graphs). Furthermore, for each yes-instance from these graph classes, we show that a linear number of flip operations is sufficient and we can exhibit a corresponding sequence of flip operations in polynomial time.
Cite as

Marthe Bonamy, Nicolas Bousquet, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Arnaud Mary, Moritz Mühlenthaler, and Kunihiro Wasa. The Perfect Matching Reconfiguration Problem. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 80:1-80:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bonamy_et_al:LIPIcs.MFCS.2019.80,
  author =	{Bonamy, Marthe and Bousquet, Nicolas and Heinrich, Marc and Ito, Takehiro and Kobayashi, Yusuke and Mary, Arnaud and M\"{u}hlenthaler, Moritz and Wasa, Kunihiro},
  title =	{{The Perfect Matching Reconfiguration Problem}},
  booktitle =	{44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  pages =	{80:1--80:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-117-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{138},
  editor =	{Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.80},
  URN =		{urn:nbn:de:0030-drops-110248},
  doi =		{10.4230/LIPIcs.MFCS.2019.80},
  annote =	{Keywords: Combinatorial Reconfiguration, Graph Algorithms, Perfect Matching}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.48
Complexity of the Multi-Service Center Problem

Authors: Takehiro Ito, Naonori Kakimura, and Yusuke Kobayashi

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
The multi-service center problem is a variant of facility location problems. In the problem, we consider locating p facilities on a graph, each of which provides distinct service required by all vertices. Each vertex incurs the cost determined by the sum of the weighted distances to the p facilities. The aim of the problem is to minimize the maximum cost among all vertices. This problem is known to be NP-hard for general graphs, while it is solvable in polynomial time when p is a fixed constant. In this paper, we give sharp analyses for the complexity of the problem from the viewpoint of graph classes and weights on vertices. We first propose a polynomial-time algorithm for trees when p is a part of input. In contrast, we prove that the problem becomes strongly NP-hard even for cycles. We also show that when vertices are allowed to have negative weights, the problem becomes NP-hard for paths of only three vertices and strongly NP-hard for stars.
Cite as

Takehiro Ito, Naonori Kakimura, and Yusuke Kobayashi. Complexity of the Multi-Service Center Problem. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 48:1-48:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{ito_et_al:LIPIcs.ISAAC.2017.48,
  author =	{Ito, Takehiro and Kakimura, Naonori and Kobayashi, Yusuke},
  title =	{{Complexity of the Multi-Service Center Problem}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{48:1--48:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.48},
  URN =		{urn:nbn:de:0030-drops-82536},
  doi =		{10.4230/LIPIcs.ISAAC.2017.48},
  annote =	{Keywords: facility location, graph algorithm, multi-service location}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.13
The Directed Disjoint Shortest Paths Problem

Authors: Kristof Berczi and Yusuke Kobayashi

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
In the k disjoint shortest paths problem (k-DSPP), we are given a graph and its vertex pairs (s_1, t_1), ... , (s_k, t_k), and the objective is to find k pairwise disjoint paths P_1, ... , P_k such that each path P_i is a shortest path from s_i to t_i, if they exist. If the length of each edge is equal to zero, then this problem amounts to the disjoint paths problem, which is one of the well-studied problems in algorithmic graph theory and combinatorial optimization. Eilam-Tzoreff (1998) focused on the case when the length of each edge is positive, and showed that the undirected version of 2-DSPP can be solved in polynomial time. Polynomial solvability of the directed version was posed as an open problem by Eilam-Tzoreff (1998). In this paper, we solve this problem affirmatively, that is, we give a first polynomial time algorithm for the directed version of 2-DSPP when the length of each edge is positive. Note that the 2 disjoint paths problem in digraphs is NP-hard, which implies that the directed 2-DSPP is NP-hard if the length of each edge can be zero. We extend our result to the case when the instance has two terminal pairs and the number of paths is a fixed constant greater than two. We also show that the undirected k-DSPP and the vertex-disjoint version of the directed k-DSPP can be solved in polynomial time if the input graph is planar and k is a fixed constant.
Cite as

Kristof Berczi and Yusuke Kobayashi. The Directed Disjoint Shortest Paths Problem. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{berczi_et_al:LIPIcs.ESA.2017.13,
  author =	{Berczi, Kristof and Kobayashi, Yusuke},
  title =	{{The Directed Disjoint Shortest Paths Problem}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{13:1--13:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.13},
  URN =		{urn:nbn:de:0030-drops-78246},
  doi =		{10.4230/LIPIcs.ESA.2017.13},
  annote =	{Keywords: Disjoint paths, shortest path, polynomial time algorithm}
}
Document
DOI: 10.4230/LIPIcs.STACS.2012.206
Edge-disjoint Odd Cycles in 4-edge-connected Graphs

Authors: Ken-ichi Kawarabayashi and Yusuke Kobayashi

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract
Finding edge-disjoint odd cycles is one of the most important problems in graph theory, graph algorithm and combinatorial optimization. In fact, it is closely related to the well-known max-cut problem. One of the difficulties of this problem is that the Erdös-Pósa property does not hold for odd cycles in general. Motivated by this fact, we prove that for any positive integer k, there exists an integer f(k) satisfying the following: For any 4-edge-connected graph G=(V,E), either G has edge-disjoint k odd cycles or there exists an edge set F subseteq E with |F| <= f(k) such that G-F is bipartite. We note that the 4-edge-connectivity is best possible in this statement. Similar approach can be applied to an algorithmic question. Suppose that the input graph G is a 4-edge-connected graph with n vertices. We show that, for any epsilon > 0, if k = O ((log log log n)^{1/2-epsilon}), then the edge-disjoint k odd cycle packing in G can be solved in polynomial time of n.
Cite as

Ken-ichi Kawarabayashi and Yusuke Kobayashi. Edge-disjoint Odd Cycles in 4-edge-connected Graphs. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 206-217, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{kawarabayashi_et_al:LIPIcs.STACS.2012.206,
  author =	{Kawarabayashi, Ken-ichi and Kobayashi, Yusuke},
  title =	{{Edge-disjoint Odd Cycles in 4-edge-connected Graphs}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{206--217},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.206},
  URN =		{urn:nbn:de:0030-drops-34173},
  doi =		{10.4230/LIPIcs.STACS.2012.206},
  annote =	{Keywords: odd-cycles, disjoint paths problem, Erd\"{o}s-Posa property, packing algorithm, 4-edge-connectivity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2012.278
Linear min-max relation between the treewidth of H-minor-free graphs and its largest grid

Authors: Ken-ichi Kawarabayashi and Yusuke Kobayashi

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract
A key theorem in algorithmic graph-minor theory is a min-max relation between the treewidth of a graph and its largest grid minor. This min-max relation is a keystone of the Graph Minor Theory of Robertson and Seymour, which ultimately proves Wagner's Conjecture about the structure of minor-closed graph properties. In 2008, Demaine and Hajiaghayi proved a remarkable linear min-max relation for graphs excluding any fixed minor H: every H-minor-free graph of treewidth at least c_H r has an r times r-grid minor for some constant c_H. However, as they pointed out, there is still a major problem left in this theorem. The problem is that their proof heavily depends on Graph Minor Theory, most of which lacks explicit bounds and is believed to have very large bounds. Hence c_H is not explicitly given in the paper and therefore this result is usually not strong enough to derive efficient algorithms. Motivated by this problem, we give another (relatively short and simple) proof of this result without using big machinery of Graph Minor Theory. Hence we can give an explicit bound for c_H (an exponential function of a polynomial of |H|). Furthermore, our result gives a constant w=2^O(r^2 log r) such that every graph of treewidth at least w has an r times r-grid minor, which improves the previously known best bound 2^Theta(r^5)$ given by Robertson, Seymour, and Thomas in 1994.
Cite as

Ken-ichi Kawarabayashi and Yusuke Kobayashi. Linear min-max relation between the treewidth of H-minor-free graphs and its largest grid. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 278-289, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{kawarabayashi_et_al:LIPIcs.STACS.2012.278,
  author =	{Kawarabayashi, Ken-ichi and Kobayashi, Yusuke},
  title =	{{Linear min-max relation between the treewidth of H-minor-free graphs and its largest grid}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{278--289},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.278},
  URN =		{urn:nbn:de:0030-drops-34165},
  doi =		{10.4230/LIPIcs.STACS.2012.278},
  annote =	{Keywords: grid minor, treewidth, graph minor}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact